| A-Files: Installieren | Algorithmen in C |

Beim Programmieren treten oft viele Probleme auf, die auf ähnliche Weise gelöst werden können. Oft unterscheiden sich die Lösungsansätze aber stark in ihrer Effizienz und ihrem Speicherverbrauch. Weshalb aber soll jeder das Rad für sich alleine erfinden, wo doch eine Reihe von leistungsfähigen Algorithmen publik gemacht wurden, die dem gestreßten Programmierer das Leben sehr erleichtern können und oftmals besser mit den Resourcen des Computers umgehen als allfällige triviale Lösungen.

Viele Probleme können recht einfach gelöst werden, wenn man die richtige Datenstruktur und den richtigen Algorithmus verwendet. Dieser Kurs soll Ihnen vor allem helfen, die wichtigsten Datenstrukturen zu verstehen, um in weiterer Folge dann abschätzen zu können, welche Datenstruktur für die Lösung eines speziellen Problems am besten geeignet ist. Eng verknüpft mit dem Begriff der Datenstruktur sind damit verbundene Algorithmen, die zur Behandlung der Datenstruktur dienen. Die enge Verbindung zwischen diesen beiden Begriffen läßt sich beispielsweise in modernen Programmiermethoden wie z.B. der OOP (objektorientierte Programmierung) wiederfinden, in der die Daten und die damit operierenden Algorithmen (Methoden) prinzipiell zusammengehören und eine Klasse bilden (Kapselungsprinzip). Die zu den Datenstrukturen gehörigen Algorithmen stellen die Operationen zur Verfügung, die mit der Datenstruktur möglich sind. Für diese Art der Darstellung wäre natürlich eine objektorientierte Programmiersprache ideal. Da auf dem AMIGA aber C die vorherrschende Programmiersprache ist, sind alle abgedruckten Programme in C geschrieben. An dieser Stelle soll aber auch einmal mit dem Vorurteil aufgeräumt werden, daß man Programmiersprachen in objektorientierte und nicht objektorientierte einteilen kann. OOP ist eine Programmiermethode und kein Sprachmerkmal. Sogenannte "objektorientierte Programmiersprachen" unterstützen nur die Prinzipien der OOP in ihrem Sprachkonzept. Das bedeutet aber nicht, daß man in nicht objektorientierten Sprachen nicht objektorientiert programmieren kann. Kenner des AMIGA-Betriebssystem werden beispielsweise auch objektorientierte Ansätze im Amiga-OS finden. Das beste Beispiel für das Vererbungsprinzip sind die Nodes. Die Node dient als Basisklasse, auf dieser baut beispielsweise die Task-Struktur auf. Von dieser wird dann noch die Process-Klasse abgeleitet. Der Vorteil eines solchen Aufbaus liegt ja wohl klar auf der Hand. Da sowohl die Task- als auch die Process-Klasse (wie viele andere auch) von der Basisklasse Node abgeleitet wurde, können alle Operationen der Klasse Node auch auf die abgeleiteten Klassen angewandt werden. Zu diesen Operationen gehören die Exec-Funktionen AddHead, AddTail, RemHead, RemTail, Insert, Enqueue und Remove.

Diese Vorgehensweise erlaubt also eine recht vielseitige Verwendung der oben genannten Operationen auf verschiedenste Dinge. Aus diesem Grund habe ich es als notwendig erachtet, bestimmte objektorientierte Ansätze auch in manchen der in diesem Kurs vorkommenden Programmen zu verwirklichen. Denn obwohl ich die OOP nicht - wie so viele - als Allheilmittel gegen die Software-Krise betrachte, bin ich doch der Meinung, daß auch auf dem AMIGA C früher oder später seinem Nachfolger C++ den Rang ablaufen wird. Deshalb wollen wir hier einmal kurz besprechen, welche Ansätze wir bei manchen unserer Implementierungen übernehmen wollen. Zuerst legen wir einmal fest, daß jeder Vertreter aller unserer zukünftigen Datentypen einen Constructor und einen Destructor haben kann (aber nicht muß). Der Constructor ist immer die Funktion, die vor der ersten Verwendung der Datenstruktur aufgerufen werden muß. Er versetzt die Datenstruktur in einen definierten Anfangszustand. Der Destructor hingegen wird dann verwendet, wenn das Objekt seinen Zweck erfüllt hat und in Zukunft nicht mehr verwendet wird. Er gibt im allgemeinen alle belegten Resourcen wieder frei.

Weiters definieren wir zu einem Objekt immer alle darauf anwendbaren Operationen. Damit legen wir fest, was mit einem Vertreter dieses (abstrakten) Datentyps alles gemacht werden kann. Die Operationen werden als einfache C-Funktionen implementiert, deren erstes Argument mit dem Namen this immer ein Zeiger auf das Objekt ist, auf das die Operation angewandt werden soll. Dies sollte es alle jenen, die stolze Besitzer eines C++-Compilers sind, möglich machen, die Funktionen schnell in das objektorientierte Konzept dieser Programmiersprache umzugestalten.

Beginnen wir nun aber mit der ersten, zugegebenermaßen noch etwas einfachen Datenstruktur, der linearen Liste. Wie Sie sicherlich wissen, ist eine einfache Implementation dieser Datenstruktur schon im Betriebssystem zu finden, nämlich die oben erwähnte Node zusammen mit der List. Es handelt sich dabei um die einfachste Grundform einer linearen Liste mit doppelter Verkettung. Ich möchte nicht genauer darauf eingehen, da der AMIGA-Kenner sicherlich mit dem Umgang den Standardfunktionen des Betriebssystems vertraut ist. Vielmehr wollen wir uns einmal mit der allgemeinen Beschaffenheit linearer Listen und ihren vielfältigen Variationsmöglichkeiten befassen. Da die Datenstruktur "Liste" in ihrer einfachsten Form nicht sonderlich kompliziert ist, soll sie auch als Beispiel dienen, wie wir im folgenden unsere sicherlich komplizierter werdenden Datenstrukturen aufzubauen gedenken.

Eine Liste dient immer zur Speicherung von Daten, die in irgendeiner Form zusammengehören. Als Operationen auf die Datenstruktur Liste definieren wir folgende Funktionen: Einfügen eines bestimmten Elementes, Entfernen eines Elementes und Suchen eines Elementes. Die Definition der Datenstruktur Liste und der darauf definierten Funktionen (Methoden) bilden hierauf eine sogenannte Klasse. Die einfachste Form einer linearen Liste, die oft nicht als solche erkannt wird, ist die Speicherung in Form eines Arrays. Dabei werden die Elemente einfach nacheinander angereiht (sequentielle Speicherung linearer Listen). Soll nun in diesem Feld ein Element an einer bestimmten Stelle eingefügt werden, müssen alle nachfolgenden Elemente um eine Position zurückverschoben werden. Ähnlich müssen beim Entfernen eines bestimmten Elementes alle Elemente danach um eine Position nach vorne geschoben werden. Damit offenbart sich schon der größte Nachteil der Listen in Form eines Arrays: wenn man nicht gerade mit dem letzten Element des Arrays operiert, können die Einfüge- und Entferne-Operationen sehr aufwendig werden. Auch der Umstand, daß ein Feld immer eine bestimmte Größe hat und somit nur eine begrenzte Anzahl von Elementen aufnehmen kann, schränkt die Verwendung von Arrays als Listen stark ein. Das Suchen in Feldern geht jedoch sehr schnell vonstatten, besonders wenn die Listen sortiert gehalten werden. Dieser Vorteil rechtfertigt, daß wir uns mit den Arrays als Listen doch noch genauer beschäftigen wollen. Wird nämlich nur sehr, sehr selten eingefügt und entfernt, jedoch häufig ein Element in der Liste gesucht, hat die Verwendung von Feldern durchaus ihre Berechtigung. Wir kommen deshalb später bei den Suchvorgängen nocheinmal auf eine Liste dieser Form zurück.

Nun wollen wir aber die wohl häufigste Form der Speicherung von Listen betrachten: die verkettete Speicherung linearer Listen. Hier wird mit den einzelnen Elementen jeweils ein Pointer auf das nachfolgende Element mitgespeichert. Mit dem zusätzlichen Speicheraufwand erkauft man sich viele Vorteile. Die Einfüge- und Entferne-Operationen reduzieren sich auf das Umstellen von Pointern und gehen somit recht schnell vonstatten. Zusätzlich können jederzeit neue Elemente an die Liste angehängt werden, solange noch genügend Speicher zur Verfügung steht, es muß also nicht von vornherein ein bestimmtes Fassungsvermögen der Liste festgelegt werden, wie das bei den Feldern der Fall war. Um auf die Liste zugreifen zu können, wird irgendwo im Programm die Adresse des ersten Elements gemerkt. Zusätzlich legen wir fest, daß die Liste genau dann leer ist, wenn dieser Zeiger NULL ist.

Um nun die verkettete Liste vollständig definiert zu haben, müssen wir noch besprechen, wie die einzelnen Operationen auszusehen haben. Die Einfüge-Operation ist trivial. Probleme gibt es jedoch beim Entfernen eines bestimmten Elementes, da dessen Vorgänger, der den Zeiger auf das zu entfernende Element enthält, nicht bekannt ist. Für dieses Problem bieten sich zwei offensichtliche Lösungen an. Einerseits könnte man die Liste von Anfang an durchlaufen und sich den gesuchten Vorgänger merken, andererseits könnte man natürlich auch eine Rückverkettung vornehmen, d.h. jedes Element einer Liste enthält außer dem Zeiger auf das nächste Element noch einen weiteren Pointer auf den Vorgänger. Während die erste Methode für lange Listen schnell untragbar langsam wird, geht die zweite Methode stark zu Lasten des Speichers, da für jedes gespeicherte Element weitere vier Bytes benötigt werden. Handelt es sich um homogene Listen, also Listen, in denen nur gleiche Elemente gespeichert werden, und ist zusätzlich die Größe der einzelnen Knoten bekannt (und nicht allzu groß), dann bietet sich ein nützlicher Trick an (s. Abbildung 1). Dabei kopiert man den Nachfolger des zu entfernenden Elementes k, der ja bekannt ist, an die Adresse von k. Dieses Verfahren funktioniert aber genau dann nicht, wenn das zu entfernende Element k das letzte Element der Liste ist und somit keinen Nachfolger hat. Um diesen Spezialfall auch behandeln zu können, benützt man einen oft gesehenen Trick, nämlich die Verwendung von Dummy-Elementen, die ja auch bei den EXEC-Lists vorkommen. Dabei hängen wir einfach an das Ende der Liste ein Element, das keinerlei Informationen trägt. Weiterhin legen wir fest, daß das Dummy-Element am Ende der Liste (der sog. Tail oder Schwanz der Liste) immer auf seinen Vorgänger zeigt, oder auf NULL, wenn die Liste leer ist. Durch dieses Tail-Element gewährleisten wir, daß jedes zu entfernende Element einen Nachfolger hat, und unser Trick von vorhin funktioniert wieder in jedem Fall. Sie sehen also, wie durch einfache Kniffe viel an Laufzeit und Speicherplatz eingespart werden kann.

Abb. 1: Entfernen durch Umkopieren.

Wie oben erwähnt, können durch die verkettete Speicherung die Operationen Einfügen und Entfernen recht rasch ausgeführt werden. Die Suchoperation läßt sich jedoch nicht so effizient gestalten, wie bei den Arrays. Dennoch gibt es verschiedene Strategien, um ein gewünschtes Element in der Liste schnell aufzufinden. Bevor wir uns aber mit dem Suchen im Detail beschäftigen, wollen wir einmal klären, was wir unter "Suchen" eigentlich verstehen. Dazu teilen wir die in einem Knoten gespeicherte Information in die sogenannte Schlüsselinformation - oder einfach nur kurz den Schlüssel - und in die Begleitinformation ein. Wenn wir nun ein bestimmtes Element suchen, wird nur der Schlüssel zum Vergleich herangezogen, die Begleitinformation ist hierfür irrelevant. Im Falle der EXEC-Lists ist der Schlüssel beispielsweise das ln_Name Feld, nach dem die Liste mittels FindName abgesucht werden kann. Allfällige hinten angehängte Daten, wie z.B. die Task-Informationen werden für die Suche nicht in Betracht gezogen, es handelt sich dabei also um Begleitinformationen.

Betrachten wir vorerst einmal die Suchoperationen für Listen, die als Arrays gespeichert sind. Die wohl einfachste, aber auch ineffiziente Methode ist, jedes Element des Feldes der Reihe nach mit dem gesuchten Schlüssel zu vergleichen bis entweder eine Übereinstimmung festgestellt werden konnte (erfolgreiche Suche) oder das Ende der Liste erreicht wurde (erfolglose Suche). Es erscheint plausibel, daß diese Methode nicht besonders schnell ist, da im schlechtesten Fall alle Elemente des Feldes zum Vergleich herangezogen werden müssen. Wir wollen deshalb einen Algorithmus kennenlernen, der für die gleiche Aufgabe viel weniger Zeit in Anspruch nimmt: das binäre Suchen.

Grundvoraussetzung für diese Suchstrategie ist, daß die Liste nach ihren Schlüsseln aufsteigend sortiert sein muß, das bedeutet, der kleinste Schlüssel steht ganz am Anfang des Feldes und der größte an dessen Ende. Zusätzlich sollte die Anzahl der in der Liste enthaltenen Schlüsseln bekannt sein. Das binäre Suchen läßt sich am besten rekursiv beschreiben. Es beginnt mit dem Vergleich bei dem Element, das in der Mitte der Liste steht, nennen wir es k. Ist nun der Schlüssel von k gleich dem Schlüssel des gesuchten Elementes s, dann sind wir fertig. Falls k aber größer als s ist, wird aus den verbleibenden Elementen, die kleiner als k sind, wieder das mittlere herausgesucht. Ist k jedoch kleiner als s, dann setzt der Algorithmus mit dem Vergleich der Elemente rechts von k fort, indem er von diesen das mittlere heraussucht. Wie Sie sehen, fällt bei jedem Vergleich die Hälfte der Elemente unter den Tisch, nämlich entweder alle Knoten links oder rechts von k. Aus diesem Grund ist die binäre Suche auch viel schneller als die sequentielle Suche. Listing 1 zeigt ein Beispiel einer Implementation des binären Suchens einer Integerzahl in einem sortierten Feld.

Wie Sie vielleicht wissen, ist auch in Ihrer C-Standardbibliothek eine Version des binären Suchens vorhanden, die auf jeden beliebigen Datentyp angewandt werden kann. Die Routine benützt dazu einen Trick, der auch bei der Sortierfunktion qsort angewandt wurde. Der bsearch-Funktion werden folgende Parameter übergeben: ein Zeiger auf das gesuchte Objekt, die Basis des Feldes mit den einzelnen Elementen, die Anzahl der darin gespeicherten Elemente und die Größe eines einzelnen in Bytes. Als letzter Parameter wird ein Zeiger auf eine Funktion erwartet, mit deren Hilfe zwei Elemente verglichen werden können. Diese Funktion erhält als Übergabeparameter zwei Zeiger auf Objekte des zu vergleichenden Typs. Wenn die beiden Objekte - nennen wir sie p und q - gleich sind, soll diese Funktion 0 zurückgeben, ist p kleiner als q (bzw. der Schlüssel von p kleiner als der von q), dann muß ein Wert kleiner 0 zurückgegeben werden, ansonsten ein Wert größer 0. Diese Vorgehensweise erlaubt, daß bsearch selber keine Ahnung hat, um welchen Datentyp es sich bei dem Feld handelt. Es ruft einfach nur die Vergleichsfunktion auf, die einzig und allein um den Datentyp Bescheid weiß. Auch wir werden in späteren Folgen auf solche Weise vorgehen.

Eine Erweiterung der Idee des binären Suchens ist die Interpolationssuche, bei der man versucht, die Position des Elementes schon im voraus abzuschätzen. Hier macht man sich eine Idee zunutze, die man auch im täglichen Leben beobachten kann: das Interpolieren. Nehmen wir einmal an, Sie suchen den Namen "Berger" in einem Telefonbuch. Dann würde Sie sicher nie auf die Idee kommen, das Telefonbuch in der Mitte aufzuschlagen und dort die Suche zu beginnen, sondern Sie schlagen das Telefonbuch automatisch relativ weiter vorne auf, da Sie wissen, daß der Buchstabe "B" eher am Anfang des Alphabets zu finden ist. Obwohl Sie sich wahrscheinlich dessen nicht bewußt sind, machen Sie damit eine Interpolation. Dasselbe wollen wir uns nun auch beim Interpolationssuchen zunutze machen. Anstatt das Feld durch m=l+(r-l)/2 streng in der Mitte zu teilen, schätzen wir die zu erwartende Position durch Miteinbeziehung der Schlüsselinformation ab: m=l+(s-k[l])/(k[r]-k[l])*(r-l). Durch diese Abschätzung kann bei relativ gleichverteilten Listen gegenüber dem binären Suchen noch an Geschwindigkeit gewonnen werden. Beachten Sie aber bitte, daß durch die aufwendigere Berechnung und durch den Umstand, daß im schlechtesten Fall alle Elemente mit dem gesuchten Schlüssel verglichen werden müssen, die Interpolationssuche auch sehr langsam werden kann.

Wie leicht einzusehen ist, eignen sich diese Suchmethoden nicht für die verkettete Speicherung von linearen Listen, da beispielsweise nicht ohne weiteres auf das mittlere Element zugegriffen werden kann. Wenn man hier ein Element in der Liste sucht, muß man jedes einzelne Element nacheinander mit dem gesuchten Schlüssel vergleichen. Es ist nicht schwer zu erkennen, daß die Effizienz dieser Suchstrategie stark davon abhängt, wie weit vorne das gesuchte Element in der Liste steht. Deshalb versucht man, Elemente, nach denen häufiger gesucht wird, weiter an den Anfang der Liste zu stellen als jene, die weniger häufig benötigt werden. Solche Listen nennt man auch selbstanordnende Listen und es gibt verschiedene Regeln, nach denen sie gebildet werden. Ich möchte an dieser Stelle die drei gebräuchlichsten Typen vorstellen.

Die Move-to-front-Regel sieht vor, daß ein Element, auf das (durch eine Suche) zugegriffen wurde, an den Anfang der Liste zu stellen ist. Dadurch befinden sich statistisch jene Elemente, die häufig benötigt werden, nach einer gewissen Einarbeitungszeit eher am Anfang der Liste. Andererseits kann es natürlich passieren, daß auf ein Element zugegriffen wird, daß eigentlich sehr selten benötigt wird, und dieses dann ziemlich lange relativ weit am Anfang der Liste steht.

Dies ist bei der zweiten Methode, der Transpose-Regel, nicht so krass. Hier wird ein Element, auf das zugegriffen wurde, mit seinem Vorgänger vertauscht. Auch dadurch kommen die häufiger benützten Elemente langsam an den Beginn der Liste. Dieses Verfahren benötigt hingegen eine größere Einarbeitungszeit, macht dafür aber weniger Fehler als die Move-to-front-Regel, da die Elemente nur relativ langsam wandern.

Die dritte Methode nennt sich Frequency Count und basiert auf einer eher primitiven Idee. Es wird einfach zu jedem Knoten ein Zähler mitgespeichert, der angibt, wie oft auf dieses Element zugegriffen worden ist. Die Liste wird dann immer nach diesem Zähler absteigend sortiert gehalten, sodaß das am häufigsten benutzte Element immer am Anfang steht. Diese Methode benötigt aber enorm viel zusätzlichen Speicherplatz und ist nicht viel besser als die Move-to-front-Regel, sodaß sie nur zur Anwendung kommen sollte, wenn die Anzahl der Zugriffe sowieso im Knoten mitgespeichert werden. Die beiden anderen Regeln sind ungefähr gleich gut geeignet. Welcher von beiden der Vorzug gegeben werden soll, ist schwer zu beantworten. In der Literatur wird oftmals die Move-to-front-Regel favorisiert, obwohl auch die Transpose-Regel bei langer Laufzeit durch ihre Stabilität besticht. Grundsätzlich kann gesagt werden, daß, egal für welche Regel man sich dann schlußendlich entscheidet, sich die Verwendung von selbstanordnenden Listen anstatt normaler verketteter Listen sicherlich auszahlt, da der Mehraufwand für das oftmalige Umordnen durch den Geschwindigkeitsgewinn beim Suchen mehr als wettgemacht wird. Trotzdem sind die linearen Listen für den Suchvorgang nicht die beste Wahl, weshalb wir im Verlauf dieses Kurses noch eine Datenstruktur kennenlernen werden, die sich dafür besser eignet und die eine Art von binärer Suche auch bei verketteter Speicherung zuläßt.

Kursübersicht:

Teil 1 -- Einführung und lineare Listen.
Teil 2 -- Der Stapel und seine Anwendung.
Teil 3 -- Der Baum.
Teil 4 -- Anwendung von Bäumen.
Teil 5 -- Hashverfahren
Teil 6 -- Sortieren

Markus Öllinger ...........

Abb. 1: Entfernen durch Umkopieren.
Programmierlisting (shift-click!)